package fr.kyvos.optimization;

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.logging.FileHandler;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.util.logging.SimpleFormatter;

/**
 * Class KnapSackProblem
 *
 * @file KnapSackProblem.java
 * @author fr.kyvos
 * @date 01 January 2013
 *
 */

public class KnapSackProblem {

	protected int mNbItems;			// number of items
	protected ArrayList<KspItem> mItemsList;	// list of items
	protected double mCapacity;		// capacity of the sack
    
	protected Random mRandom;		// random generator
	private BufferedReader mBufred;

	protected KspSolution mBestSolution;        // best solution
	
	protected ArrayList<KspSolution> mPopulation; // population

	/**
	 * Constructor
     * Create from a KPS file
     * 
	 * @param pC
	 * @param pFilename
	 */
	public KnapSackProblem(String pFilename) throws Exception {
		super();
		mItemsList = new ArrayList<KspItem>(); 
        KspItem lItem = null;
		mRandom = new Random();
        String lStr,lName;
        Double lP,lW;
        ArrayList<String> lAStr;
        FileReader lFich = new FileReader(pFilename);
                
        mBufred = new BufferedReader(lFich);
        lStr = mBufred.readLine();
        lAStr = StringToArrayList(lStr);
        lName = lAStr.get(1).toString();
        lStr = mBufred.readLine();
        lAStr = StringToArrayList(lStr);
        mNbItems = Integer.parseInt((lAStr.get(1)).toString());
        lStr = mBufred.readLine();
        lAStr = StringToArrayList(lStr);
        mCapacity = Double.parseDouble((lAStr.get(1)).toString());
        lStr = mBufred.readLine();      // separation line
        for (int i=0; i<mNbItems; i++) {
        	lStr = mBufred.readLine();
            lAStr = StringToArrayList(lStr);
            lName = lAStr.get(0).toString();
            lStr = mBufred.readLine();
            lAStr = StringToArrayList(lStr);
            lW = Double.parseDouble((lAStr.get(1)).toString());
            lStr = mBufred.readLine();
            lAStr = StringToArrayList(lStr);
            lP = Double.parseDouble((lAStr.get(1)).toString());
            // item creation
            lItem = new KspItem(lName,lP,lW);
            mItemsList.add(lItem);        	
        }
		mBestSolution = new KspSolution(mNbItems);
	}
	
	/**
	 * Calculate the fitness of a solution
	 * 
	 * @param pSolution
	 */
	public void calculateFitness(KspSolution pSolution) {
		double lFitness = 0.0;
    	double lProfit = 0.0;
    	double lWeight = 0.0;
	    
		for (int i=0;i<mNbItems;i++) {
			if (pSolution.mValues.get(i)) {
				lWeight += mItemsList.get(i).getWeight();
	    		lProfit += mItemsList.get(i).getProfit();
			}
		}
		if (lWeight<mCapacity) {
			lFitness = lProfit;
		}
		else {
			lFitness = 0.0;
		}
		pSolution.setWeight(lWeight);
		pSolution.setProfit(lProfit);
		pSolution.setFitness(lFitness);
	}

	/**
	 * Begin the KnapSack Problem
	 * @throws IOException 
	 */
	public void initiate() throws IOException {
		
		/*
		File file = new File("29052013-1742.txt");
		FileWriter f = new FileWriter(file.getAbsoluteFile());
		BufferedWriter out = new BufferedWriter(f);
		*/
		//System.out.println(mItemsList.get(0).getWeight());
		// ALGORITHM !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
		KspSolution meilleuresolution;

		mBestSolution.setRandomTrueValues(6, new Random());
		calculateFitness(mBestSolution);
		
		//doMethodeTaboue(4, 10);
		try {
			mBestSolution = algo_genetique(100, 2000, KspSolution.ROULETTE_BIAISEE_RANDOM, 0.01);
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		/*
		for (int i =0;i<50;i++)
		{
			System.out.println("solution "+i+"\n");
			meilleuresolution=RecuitSimule(800, 150, 100, 0.99);
			out.write(i+";meilleure solution :"+meilleuresolution.getFitness());
			out.flush();
		}
		
		out.close();
		*/
		System.out.println("Best des BEST Solution: "+mBestSolution.toString());
	}
	
	/**
	 * Initialise la premiere solution de base en placant d'abord les items
	 * qui ont le meilleur ratio
	 */
	public void initFirstSolutionRatio() {
		//System.out.println("initFirstSolutionRatio");
		// liste de positions
		ArrayList<Integer> itemPositionList = new ArrayList<Integer>(mNbItems);
		for (int i=0; i<mNbItems; i++) {
			//System.out.println("init i : "+i);
			itemPositionList.add(new Integer(i));
		}
		
		// algo de tri en fonction du ratio (descendant)
		boolean change = true;
		if (mItemsList.size()>1) {
			while (change) {
				// s'il y a eu un changement, on recommence
				// on arrete si plus de chgt
				
				// pour l'instant, false
				change = false;
				
				KspItem item_courant;
				KspItem item_precedent;
				for (int i = 1 ; i<mNbItems; i++) {
					//System.out.println("tri i : "+i);
					item_courant = mItemsList.get(itemPositionList.get(i));
					item_precedent = mItemsList.get(itemPositionList.get(i-1));
					Integer pos_removed;
					if (item_courant.getmRatio() > item_precedent.getmRatio()){
						//System.out.println("item_courant.getmRatio() : "+item_courant.getmRatio()+" - item_precedent.getmRatio() : "+item_precedent.getmRatio());
						// place l'element courant avant l'element precedent car
						// son ratio est plus grand
						pos_removed = itemPositionList.get(i);
						itemPositionList.remove(i);
						itemPositionList.add(i-1, pos_removed);
						// il y eu au moins un chgt
						change = true;
					}
				}
				//System.out.println("change ? "+change);
			}
		}
		
		//System.out.println("liste des posistions triees : "+itemPositionList.toString());
		
		Iterator<Integer> iter = itemPositionList.iterator();
		Integer position;
		int i = 0;
		boolean go_on = true;
		// on boucle sur la liste des positions
		while (iter.hasNext() && go_on) {
			position = iter.next();
			KspItem item = mItemsList.get(position);
			
			// on essaie de voir si en ajoutant l'item, on ne depasse pas la
			// capacite
			go_on = ((mBestSolution.getWeight()+item.getWeight()) <= mCapacity);
			if (go_on) {
				mBestSolution.addItem(itemPositionList.get(i), item);
			}
			
			i++;
		}
		
		calculateFitness(mBestSolution);
		
		System.out.println("Solution initialisee avec ration : \n"+mBestSolution.toString()+"\n\n");
	}
	
	@SuppressWarnings("deprecation")
	public void doMethodeTaboue(int tabou_list_size_max, int number_of_tests) throws SecurityException, IOException{
		Logger logger = getSimpleLogger("[log]_doMethodeTaboue");
		
		logger.log(Level.INFO, "\n\n-------------------------\n");
		logger.log(Level.INFO, "---------NEW TEST--------\n");
		logger.log(Level.INFO, "-------------------------\n\n");
		logger.log(Level.INFO, "Start of tabou method");
		
		//initFirstSolutionRatio();
		mBestSolution = new KspSolution(mNbItems);
		for (int i = 0; i<mNbItems; i++) {
			mBestSolution.setValueAtPosition(i, false);
		}
		logger.log(Level.INFO, "result of initFirstSolutionRatio() : \n"+this.mBestSolution.toString()+"\n");
		
		KspSolution curr_solution = mBestSolution;
		double best_fitness = mBestSolution.getFitness();
		// liste tabou : une transition = le prochain voisin à choisir
		LinkedList<KspSolution> list_tabou = new LinkedList<KspSolution>();
		int i = 0;
		// liste voisins
		ArrayList<KspSolution> liste_voisins = new ArrayList<KspSolution>();
		KspSolution next_solution;
		
		Random rand = new Random();
		
		if (number_of_tests >= 1) {
			do {
				liste_voisins = curr_solution.Voisinnage(mItemsList,mCapacity);
				
				// on enleve les eventuels voisins interdits (trouves dans la liste tabou)
				for (int j=0; j<list_tabou.size(); j++) {
					liste_voisins.remove(list_tabou.get(j));
					//logger.log(Level.INFO, "on enleve des voisins la solution suivante : "+list_tabou.get(j));
				}
				
				//logger.log(Level.INFO, "List 'liste_voisins' => "+liste_voisins.size()+" element(s)");
				
				if (!liste_voisins.isEmpty()) {
					//int pos_voisin_to_choose = rand.nextInt(liste_voisins.size());
					int pos_voisin_to_choose = 0;
					double meilleur_fitness_voisin = 0;
					KspSolution voisin;
					
					for (int k=0; k<liste_voisins.size(); k++) {
						voisin = liste_voisins.get(k);
						calculateFitness(voisin);
						//logger.log(Level.INFO, "EVALUATE VOISIN "+k+" - fitness : "+voisin.getFitness());
						 if (voisin.getFitness() > meilleur_fitness_voisin) {
							 meilleur_fitness_voisin = voisin.getFitness();
							 pos_voisin_to_choose = k;
						 }
						
					}
					
					//logger.log(Level.INFO, "meilleur_fitness_voisin final  : "+meilleur_fitness_voisin);
					//logger.log(Level.INFO, "On choisit le voisin no "+pos_voisin_to_choose);
					next_solution = liste_voisins.get(pos_voisin_to_choose);
					//logger.log(Level.INFO, "Le voisin choisi (next_solution) est : "+next_solution);
					
					double next_fitness = next_solution.getFitness();
					// Si on ameliore la solution courante, delta_fitness sera > 0
					double delta_fitness = next_fitness - curr_solution.getFitness();
					
					logger.log(Level.INFO, "next_fitness ("+next_fitness+") - curr_solution.getFitness() ("+curr_solution.getFitness()+") = delta_fitness("+delta_fitness+")");
					
					// Si on n'ameliore pas notre solution courante
					if (delta_fitness <= 0) {
						// on s'interdit de revenir sur nos pas
						// si la transfo tabou est deja dans la liste, on ne la remet pas
						
						//list_tabou.add(curr_solution);
						
						if (!list_tabou.contains(curr_solution))
							list_tabou.add(curr_solution);
						else logger.log(Level.INFO, "La solution courante est déjà dans la liste tabou => on ne l'ajoute pas");
						
						/*
						KspSolution k = new KspSolution(mNbItems);
						k.copySolution(curr_solution);
						
						logger.log(Level.INFO, "test equality : "+k.equals(curr_solution));
						
						k.setValueAtPosition(0, !(k.getValueAtPosition(0)));
						
						logger.log(Level.INFO, "test equality : "+k.equals(curr_solution));
						*/
						
						logger.log(Level.INFO, "list_tabou.size() ("+list_tabou.size()+") > tabou_list_size_max "+tabou_list_size_max+" ? "+(list_tabou.size() > tabou_list_size_max));
						
						// si on a depasse la taill maximale de la lliste tabou, on enleve la plus ancienne transition
						if (list_tabou.size() > tabou_list_size_max) {
							list_tabou.removeFirst();
						}
						
						logger.log(Level.INFO, "NOUVELLE LISTE TABOU : \n-----------------");
						for (int l=0; l<list_tabou.size(); l++) {
							logger.log(Level.INFO, list_tabou.get(l).toString());
						}
						logger.log(Level.INFO, "-----------------");
					}
					
					//logger.log(Level.INFO, "next_fitness ("+next_fitness+") > best_fitness ("+best_fitness+") ? "+(next_fitness > best_fitness));
					
					// Si la nouvelle solution a le meillleur fitness jamais rencontré until now !
					if (next_fitness > best_fitness)
					{
						best_fitness = next_fitness;
						mBestSolution = next_solution;
						//logger.log(Level.INFO, "Best solution for now :\n"+mBestSolution.toString()+"\n");
					}
					
					curr_solution = next_solution;
				}
				
				// on a fait le test
				i++;
				
				//logger.log(Level.INFO, "test no"+i+" realise");
			}while (i < number_of_tests && !liste_voisins.isEmpty());
		}
		
		logger.log(Level.INFO, "end of tabou method => Final best solution :\n"+mBestSolution.toString());
	}
	

    /**
     * Transform a text line into an ArrayList
     * At each space, a new element is added into ArrayList
     * 
     * @param s string
     * @return list of words in ArrayList
     */
    private ArrayList<String> StringToArrayList(String s) {
        ArrayList<String> v = new ArrayList<String>();
        StringTokenizer st = new StringTokenizer(s);

        while (st.hasMoreTokens()) v.add(st.nextToken());
        return v ;
    }

    /**
     * Display the problem
     */
	public String toString() {
		StringBuilder result = new StringBuilder();
	    String newLine = System.getProperty("line.separator");
	    KspItem lItem;
	    
		result.append("KnapSack Problem:");
	    result.append(newLine);
		result.append("  "+mNbItems+" items");
	    result.append(newLine);
		result.append("  List of items (p/w):");
	    result.append(newLine);
        for (int i=0; i<mNbItems; i++) {
            lItem = (KspItem) mItemsList.get(i);
            result.append("    "+lItem.toString());
        }
		result.append("  Capacity = "+mCapacity);
	    result.append(newLine);
       	return result.toString();
    }
	
	public KspSolution RecuitSimule(int nbEssai, int nbEssaiAvtChg, int t, double facteur) throws IOException {
		
		//initFirstSolutionRatio();
		System.out.println("fitness :"+mBestSolution.getFitness());
		int taille,nbAleatoire;
		double nbAleatoireDouble;
		Random r = new Random();
		KspSolution uneListe,uneSolution;
		double diff;
		double fitnessMax;
		
		double temperature = t;
		
		System.out.println(mBestSolution.toString());
		
		uneSolution=mBestSolution;
		fitnessMax=mBestSolution.getFitness();
		
		for (int i=0; i<nbEssai;i++)
		{
			for (int y=0; y<nbEssaiAvtChg;y++)
			{
				ArrayList<KspSolution> mesVoisins = uneSolution.Voisinnage(mItemsList,mCapacity);
				taille = mesVoisins.size();
				nbAleatoire = r.nextInt(taille);
				
				uneListe = mesVoisins.get(nbAleatoire);
				
				calculateFitness(uneListe);
				calculateFitness(uneSolution);
				
				diff = uneListe.getFitness()-uneSolution.getFitness();
				
				if (diff >= 0)
				{
					uneSolution=uneListe;
					calculateFitness(uneSolution);
					if (uneSolution.getFitness()>fitnessMax)
					{
						fitnessMax=uneSolution.getFitness();
						mBestSolution=uneSolution;
					}
				}
				else
				{
					nbAleatoireDouble = r.nextDouble();
					
					if (nbAleatoireDouble<=Math.exp((-diff)/temperature))
					{
						uneSolution=uneListe;
					}
				}
			}
			temperature=temperature*facteur;
		}
		calculateFitness(mBestSolution);
		System.out.println("meilleure solution : " + mBestSolution.toString());
		
		return mBestSolution;
	}

	
	// ALGOS GENETIQUES
	/**
	 * Met a jour le fitness de chaque solution, a executer au debut de chaque iteration
	 * de l'algo genetique (juste avant la reproduction)
	 * @param population
	 * @return
	 */
	public void maj_population(ArrayList<KspSolution> population) {
		int pop_size = population.size();
		ArrayList<KspSolution> new_population = new ArrayList<KspSolution>(pop_size);
		
		KspSolution curr_solution;
		for (int i=0; i<pop_size; i++) {
			//curr_solution = population.get(i);
			calculateFitness(population.get(i));
			
			// TODO : question => controle du poids ?
			// ...
		}
	}
	
	
	public KspSolution algo_genetique(int nb_generation, int pop_size, int mode, double proba_mutation_initiale) throws Exception{
		Logger logger = getSimpleLogger("algo_genetique");
		//logger.log(Level.INFO, "---------------- Start of method 'algo_genetique' ----------------");
		
		KspSolution best_solution = null;
		double best_fitness = 0;
		
		ArrayList<KspSolution> current_pop = KspSolution.init_first_population(pop_size, mNbItems, logger);
		maj_population(current_pop);
		
		for (int i=0; i<nb_generation; i++) {
			logger.log(Level.INFO, "iteration no"+(i+1));
			
			//current_pop = KspSolution.reproduction(current_pop, mode, logger);
			current_pop = KspSolution.reproduce(current_pop);
			
			current_pop = KspSolution.croisement(current_pop);
			
			current_pop = KspSolution.mutation(current_pop, proba_mutation_initiale);
			
			for(KspSolution sol : current_pop)
			{
				calculateFitness(sol);
				System.out.println(sol);
			}
			
			//maj_population(current_pop);
			
			for (int j=0; j<current_pop.size(); j++) {
				double fitness_solution = current_pop.get(j).getFitness();
				if (fitness_solution > best_fitness)
				{
					best_fitness = fitness_solution;
					
					best_solution = new KspSolution(mNbItems);
					best_solution.copySolution(current_pop.get(j));
				}
				
			}
			
			logger.log(Level.INFO, "Best fitness :\n"+best_solution.getFitness());
		}
		
		//logger.log(Level.INFO, "---------------- End of method 'algo_genetique' ----------------");
		
		return best_solution;
	}
	
	public static Logger getSimpleLogger(String name) throws SecurityException, IOException {
		Date now = new Date();
		FileHandler handler = new FileHandler(name+"_"+now.getDate()+"-"+now.getMonth()+"-"+now.getYear()+".txt");
		handler.setFormatter(new SimpleFormatter());
		Logger logger = Logger.getLogger("");
		logger.addHandler(handler);
		
		return logger;
	}

}
